class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        left = 0 # 下界：每个分一组
        right = 0 # 上界：全部放一起
        for i in range(len(nums)):
            left = max(left, nums[i])
            right += nums[i]
        while left < right:
            mid = (left + right) >> 1
            # 第一个使得判定问题isValid得到true的位置
            if self.isValid(nums, m ,mid):
                right = mid
            else:
                left = mid + 1
        return right

    # 判定 把nums分成<=m组，每组的和<=T
    def isValid(self, nums, m, T):
        groupSum = 0
        groupCount = 1
        for i in range(len(nums)):
            if groupSum + nums[i] <= T:
                groupSum += nums[i] # 放进当前组，不超
            else:
                groupCount += 1 # 超了，新开一组
                groupSum = nums[i]
        return groupCount <= m

'''
厚
[7],[2,5,10,8]
7      25           max:25

[7,2],[5,10,8]
9       23          max:23

7+2+5  10+8
14     18           max:18

T=20

分成<=100的2组是否可行？可行。
7+2+5
10+8  1

分成<=20的2组是否可行？可行。
7+2+5
10+8


分成<=17的2组是否可行？不可行。
7+2+5
10
8
'''